﻿// 0806train04.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

/*
 最小路径和
 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。
 */

int minPathSum(vector<vector<int>>& grid)
{
    int row_size = grid.size();
    int col_size = grid[0].size();

    vector<vector<int>>dynamic_vec(row_size, vector<int>(col_size));

    //初始化第一个格子
    dynamic_vec[0][0] = grid[0][0];

    //如果只有一行
    for (int c_1=1; c_1<col_size; c_1++)
    {
        dynamic_vec[0][c_1] = dynamic_vec[0][c_1 - 1] + grid[0][c_1];
    }

    //如果只有一列
    for (int r_1=1; r_1<row_size;r_1++)
    {
        dynamic_vec[r_1][0] = dynamic_vec[r_1 - 1][0] + grid[r_1][0];
    }

    for (int r_1=1; r_1<row_size; r_1++)
    {
        for (int c_1=1; c_1<col_size; c_1++)
        {
            int last_min = min(dynamic_vec[r_1 - 1][c_1], dynamic_vec[r_1][c_1-1]);
            dynamic_vec[r_1][c_1] = last_min + grid[r_1][c_1];
        }

    }

    return dynamic_vec[row_size - 1][col_size - 1];
    //minPathSum
}


/*
 打家劫舍
 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 */
int rob(vector<int>& nums) {

    if (nums.size() == 1) return nums[0];
    if (nums.size() == 2) return max(nums[0],nums[1]);

    int vec_size = nums.size();
    vector<int>dynamic_vec(vec_size+1);

    //前0个房子，0现金
    dynamic_vec[0] = 0;

    //前1个房子 nums[0]
    dynamic_vec[1] = nums[0];
    //前2个房子 nums[1]
    dynamic_vec[2] = max(nums[0], nums[1]);

    for (int i=3; i<=vec_size; i++)
    {
        //max(前i-1个的最优, 前i-2最优+nums[i-1])
        //nums[i-1]第i个房子的金额
        dynamic_vec[i] = max(dynamic_vec[i - 1], dynamic_vec[i - 2] + nums[i-1]);

    }
    return dynamic_vec[vec_size];
    //------
}


/*
 打家劫舍II
 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
 输入：nums = [2,3,2]
 输出：3
 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
 */

int GetMax02(vector<int>&oh_vec)
{
    int vec_size = oh_vec.size();
    vector<int>dynamic_vec(vec_size + 1);

    //前0个，0
    dynamic_vec[0] = 0;
    //前1个，oh_vec[0]
    dynamic_vec[1] = oh_vec[0];
    //前2个
    dynamic_vec[2] = max(oh_vec[0], oh_vec[1]);

    for (int i=3; i<=vec_size;i++)
    {
        dynamic_vec[i] = max(dynamic_vec[i - 1], dynamic_vec[i - 2] + oh_vec[i - 1]);
    }
    return dynamic_vec[vec_size];
    //------
}

int rob02(vector<int>& nums)
{
    if (nums.size() == 1) return nums[0];
    if (nums.size() == 2) return max(nums[0], nums[1]);

    vector<int>except_head_vec(nums.begin() + 1, nums.end());
    vector<int>except_tail_vec(nums.begin(), nums.end() - 1);

    int except_head_max = GetMax02(except_head_vec);
    int except_tail_max = GetMax02(except_tail_vec);

    return max(except_head_max, except_tail_max);
    //rob02------
}

/*
 泰波那契序列 Tn 定义如下： 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
 */
int tribonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n == 2) return 1;

    vector<int>dynamic_vec(n + 1);

    dynamic_vec[0] = 0;
    dynamic_vec[1] = 1;
    dynamic_vec[2] = 1;

    for (int i=3; i<=n; i++)
    {
        dynamic_vec[i] = dynamic_vec[i - 1] + dynamic_vec[i - 2] + dynamic_vec[i - 3];
    }
    return dynamic_vec[n];
}


/*
 找出自顶向下的最小路径和
 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 11
 */

int minimumTotal(vector<vector<int>>& triangle) {

    if (triangle.size() == 1) return triangle[0][0];

    int row_size = triangle.size();
    int col_size = triangle[row_size-1].size();

    vector<vector<int>>dynamic_vec(row_size,vector<int>(col_size,INT_MAX));
    dynamic_vec[0][0] = triangle[0][0];

    //第0列只有1条路径
    for (int r=1;r<row_size;r++)
    {
        dynamic_vec[r][0] = dynamic_vec[r - 1][0]+triangle[r][0];
    }

    for (int r=1; r<row_size; r++)
    {
        int curr_col_size = triangle[r].size();
        
        for (int c=1; c<curr_col_size;c++)
        {
            int min_last_row = min(dynamic_vec[r - 1][c], dynamic_vec[r - 1][c - 1]);
            
            dynamic_vec[r][c] = min_last_row + triangle[r][c];
        }
    }

    int result = INT_MAX;
    for (int col=0; col< col_size; col++)
    {
        result = min(result, dynamic_vec[row_size - 1][col]);
    }
    return result;
    //minimumTotal
}


int main()
{
	{
        //triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
        vector<vector<int>>triangle = { {2},{3, 4},{6, 5, 7},{4, 1, 8, 3} };
        cout << minimumTotal(triangle);

        return 0;
	}

	{
        cout << tribonacci(25);
        return 0;
	}

	{
        //nums = [2,3,2] 3
        //nums = [1,2,3,1] 4
        vector<int>nums = { 1,2,3,1 };
        cout << rob02(nums);

        return 0;
	}

	{
        //nums = [1,2,3,1] 4
        vector<int>nums = { 1,2,3,1 };
        cout << rob(nums);
        return 0;
	}

    //grid = [[1,3,1],[1,5,1],[4,2,1]]
    vector<int>vec_1 = { 1,3,1 };
    vector<int>vec_2 = { 1,5,1 };
    vector<int>vec_3 = { 4,2,1 };
    vector<vector<int>>grid = { vec_1 ,vec_2 ,vec_3 };
    cout << minPathSum(grid);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
